/*
题目: 串联所有单词的子串
给定一个字符串 s 和一个字符串数组 words。 words 中所有字符串 长度相同。

 s 中的 串联子串 是指一个包含  words 中所有字符串以任意顺序排列连接起来的子串。

    例如，如果 words = ["ab","cd","ef"]， 那么 "abcdef"， "abefcd"，"cdabef"， "cdefab"，"efabcd"， 和 "efcdab" 都是串联子串。 "acdbef" 不是串联子串，因为他不是任何 words 排列的连接。

返回所有串联字串在 s 中的开始索引。你可以以 任意顺序 返回答案。
https://leetcode.cn/problems/substring-with-concatenation-of-all-words/
 */
public class FindSubstring {
    public List<Integer> findSubstring(String s, String[] words) {
        // 滑动窗口, 根据 字符串 满足个数 是否 等于 words 的个数
        // 寻找满足 words 中的单词数量 == words.length
        List<Integer> src = new ArrayList<> ();
        int n = s.length();              // 字符串 s 长度
        int wordLen = words[0].length(); // 一个单词的长度
        int wordNum = words.length;    // 单词的个数
        int sumLen = wordLen * wordNum; // 总大小
        if (sumLen > n) return src;

        // 目标哈希表
        Map<String, Integer> wordsMap = new HashMap<> ();
        for (String word : words) {
            wordsMap.put(word, wordsMap.getOrDefault(word, 0) + 1);
        }

        // 我们只需要考虑 起点为 一个单词长度范围 内的起点
        for (int i = 0; i < wordLen; i ++) {
            if (i + sumLen > n) {      // 装不下 全部单词了
                break;
            }

            Map<String, Integer> window = new HashMap<> (); // 窗口中的哈希表
            // 开始滑动, 分别为 左, 右边界 和 相等的单词数量
            int left = i, right = i, diff = 0;
            for (; right + wordLen <= n; right += wordLen) {
                String sub = s.substring(right, right + wordLen);
                if (!wordsMap.containsKey(sub)) {  // 如果中途断了
                    window.clear();               // 清空
                    diff = 0;
                    left = right + wordLen;   // 更新窗口左边界
                    continue ;
                }
                // else
                window.put(sub, window.getOrDefault(sub, 0) + 1);  // 先加上次数
                diff ++;   // 满足 条件的单词数量 + 1
                // 如果超过了应该有的 次数的话, 就会排掉, 所以最终 diff = words.length 的情况肯定是 单词出现次数都相等
                while (window.get(sub) > wordsMap.get(sub)) {      // 如果大于了, 就要窗口左移, 进行 [修正]
                    String leftSub = s.substring(left, left + wordLen);
                    // 该窗口 除了 sub , 不会出现 [大于] 的情况
                    diff --; // 满足 words 的单词 --
                    window.put(leftSub, window.get(leftSub) - 1);
                    left += wordLen;
                }
                if (diff == wordNum)
                    src.add(left);
            }
        }

        return src;
    }
}
